/**
 * 将数组做一个划分，每个子数组进行交替加减操作
 * 问能够得到的最大值是多少
 * 令Di是到i为止的最大值，则
 * Di = max{Dj + [j+1...i]之和}
 * 
 * 直接计算需要O(N^2)，需要优化
 * 因为交替加减不能简单的用前缀和
 * 注意到位置标号奇偶性相同的总是相加，奇偶性相异的总是相减
 * 求出两个前缀和Ou和Ji，分别记录奇数位置与偶数位置的前缀和
 * 
 * 然后可以分4种情况讨论（可能2种就够了）
 * 这里只说一种，假设i和j同为偶，则j+1是奇数位置，因此奇数位置相加，偶数位置相减
 * Di = max{Dj + (Ji[i] - Ji[j]) - (Ou[i] - Ou[j])}
 * 因此Di是由之前最大的 Dj + Ou[j] - Ji[j] 决定的
 * 始终维护这个值即可，记作ou，则 Di = ou + Ji[i] - Ou[i]
 * 求出Di以后，同步更新ou, 即： ou = max(ou, D[i] + Ou[i] - Ji[i])
 * 
 * 有更简单的DP方程，令Di是到i为止的最大值，则
 * Di = max(D[i-1] + Ai, D[i-2] + A[i-1]-A[i])
 * O(N)即可
 */
class Solution {
public:
    long long maximumTotalCost(vector<int> & nums) {
        using llt = long long;
        llt const INF = 0x1F2F3F4F5F6F7F8F;
        llt const NINF = -INF;

        int n = nums.size();
        nums.insert(nums.begin(), 0);
        vector<llt> Ji(n + 1, 0);
        vector<llt> Ou(n + 1, 0);
        Ji[1] = nums[1];
        for(int i=2;i<=n;i+=2){
            Ou[i] = Ou[i - 2] + nums[i];
            Ji[i] = Ji[i - 1];
            if(i + 1 <= n){
                Ou[i + 1] = Ou[i];
                Ji[i + 1] = Ji[i - 1] + nums[i + 1];
            }
        }

        // for(int i=1;i<=n;++i){
        //     cout << Ou[i] << " ";
        // }
        // cout << endl;
        // for(int i=1;i<=n;++i){
        //     cout << Ji[i] << " ";
        // }
        // cout << endl;

        vector<llt> D(n + 1, NINF);
        D[0] = 0;
        D[1] = nums[1];
        llt ou = 0;
        llt ji = D[1] + Ji[1] - Ou[1];
        for(int i=2;i<=n;i+=2){
            auto u = ou + Ji[i] - Ou[i];
            auto v = ji + Ou[i] - Ji[i];
            D[i] = max(u, v);            
            ou = max(ou, D[i] + Ou[i] - Ji[i]);

            if(i + 1 <= n){
                auto u = ji + Ou[i + 1] - Ji[i + 1];
                auto v = ou + Ji[i + 1] - Ou[i + 1];
                D[i + 1] = max(u, v);
                ji = max(ji, D[i + 1] + Ji[i + 1] - Ou[i + 1]);
            }
        }

        return D[n];
    }
};